package com.ting.test.algorithms.KMP;

import com.ting.test.algorithms.二叉树.N叉树转二叉树;

/**
 * 利用KMP算法，求解一个字符串是否在另一个字符串中
 * 并且时间复杂度为O(n)
 */
public class KMP定义 {
    public static void main(String[] args) {
        String str1 = "asdfsadSaasdd";
        String str2 = "asdf";

        int index = process(str1, str2);
    }

    /**
     * gaUge
     *
     * @param str1
     * @param str2
     * @return 返回的是符合条件的位置 如果没有符合条件的子串，则返回-1
     */
    private static int process(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() < str2.length()) {
            return -1;
        }
        final char[] arr1 = str1.toCharArray();
        final char[] arr2 = str2.toCharArray();

        int x = 0;//表示当前arr1比对的位置
        int y = 0;//表示arr2当前比对的位置

        int[] next = genNext(str2);

        while (x < arr1.length && y < arr2.length) {
            if (arr1[x] == arr2[y]) {
                x++;
                y++;
            } else if (next[y] != -1) {
                //进入到这里则表明 arr1[x] != arr2[y] 并且在arr2中 下标Y位置的前缀和后缀相等的子串是存在的
                // next数组中的元素值，即表示当前元素相同前缀的长度，也表示的是该相同前缀结尾的下一个位置，因为这个前缀总是从0位置开始
                //同时next数组中的元素值还表示了如果当前匹配不上，Y下一次要调到的位置
                y = next[y];
            } else {
                //进入到这里则表明 arr1[x] != arr2[y] 并且next[y] == -1 下标Y已经到了0位置了
                // str2已经到了头了 头部元素仍然和arr[x]不相等，说明x这个元素已经不可能匹配上了，需要str1往下走一个元素，继续开始比较
                x++;
            }
        }

        return y == arr2.length ? x - y : -1;// 如果y已经到了最后，说明在str1中有一个子串和str2相等，否则说明没有，返回-1
    }

    private static int[] genNext(String str2) {
        final char[] chars = str2.toCharArray();
        int[] next = new int[chars.length];//next存储的是下标
        next[0] = -1;//约定
        next[1] = 0;//约定
        for (int i = 2; i < chars.length; i++) {
            int n = next[i - 1];
            while (n >= 0) {
                if (chars[i - 1] == chars[n]) {//如果当前元素A的上一个元素B与B的最长公共前缀的下一个位置的元素相同，则说明A的最长公共前缀是B的前缀长度+1
                    next[i] = next[i - 1] + 1;
                    break;
                } else {
                    n = next[n];
                }
            }

            next[i] = 0;

        }
        return next;
    }


    private static int[] genNext2(String str2s) {
        final char[] str2 = str2s.toCharArray();

        if (str2.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2; // 目前在哪个位置上求next数组的值
        int cn = 0; // 当前是哪个位置的值再和i-1位置的字符比较
        while (i < next.length) {
            if (str2[i - 1] == str2[cn]) { // 配成功的时候
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}
